package sort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] keys = new int[]{38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.print("关键字序列：");
        System.out.println(Arrays.toString(keys));
        shellSort.shellSort(keys);
    }

    //希尔排序
    public void shellSort(int[] keys) {
        System.out.println("希尔排序（升序）");
        //若干趟，控制增量每趟减半
        for (int delta = keys.length / 2; delta > 0; delta /= 2) {
            //一趟分若干组，每组直接插入排序
            for (int i = delta; i < keys.length; i++) {
                int temp = keys[i], j;                                     //keys[i]是当前待插入元素
                for (j = i - delta; j >= 0 && temp < keys[j]; j -= delta)  //组内直接插入排序（升序），寻找插入位置
                    keys[j + delta] = keys[j];                             //每组元素相距delta远
                keys[j + delta] = temp;                                    //插入元素
            }
            System.out.print("delta=" + delta + "  ");
            System.out.println(Arrays.toString(keys));
        }
    }
}
